package com.hr.剑指offer.work1;

import java.util.HashMap;

/**
 * @author 周恒哲
 * @date 2020/06/12
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 **/
public class 面试题07_重建二叉树 {
    //利用原理,先序遍历的第一个节点就是根。在中序遍历中通过根 区分哪些是左子树的，哪些是右子树的
    //左右子树，递归
    HashMap<Integer, Integer> dic = new HashMap<>();//标记中序遍历
    int[] po;//保留的先序遍历
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        po = preorder;
        for(int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    /**
     * @param pre_root  先序遍历的索引
     * @param in_left  中序遍历的索引
     * @param in_right 中序遍历的索引
     */
    TreeNode recur(int pre_root, int in_left, int in_right) {
        //相等就是自己
        if(in_left > in_right) return null;
        //pre_root是在先序里面的
        TreeNode root = new TreeNode(po[pre_root]);
        // 有了先序的,再根据先序的，在中序中获 当前根的索引
        int i = dic.get(po[pre_root]);
        //左子树的根节点就是 左子树的(前序遍历）第一个，就是+1,左边边界就是left，右边边界是中间区分的idx-1
        root.left = recur(pre_root + 1, in_left, i - 1);

        root.right = recur(pre_root + i - in_left + 1, i + 1, in_right);
        return root;
    }
}
